1. Field of the Invention
This invention relates to a cryptographic key recovery system and, more particularly, to a high-availability multi-agent cryptographic key recovery system.
2. Description of the Related Art
Copending U.S. patent application filed herewith, Ser. No. 09/224,886 entitled xe2x80x9cApparatus, Method, And Computer Program Product For Achieving Interoperability Between Cryptographic Key Recovery Enabled And Unaware Systems,xe2x80x9d assigned to the International Business Machines Corporation, is incorporated herein by reference. This cited patent application describes a key recovery system.
U.S. patent application of D. B. Johnson et al., Ser. No. 08/629,815, now U.S. Pat. No. 5,815,573 filed Apr. 10, 1996, entitled xe2x80x9cCryptographic Key Recovery Systemxe2x80x9d (xe2x80x9cJohnson et al. Ixe2x80x9d), assigned to the International Business Machines Corporation, is incorporated herein by reference. This cited patent application describes a key recovery system using multiple key recovery agents.
U.S. patent application of D. B. Johnson et al., Ser. No. 08/681,679, now U.S. Pat. No. 5,796,830 filed Jul. 29, 1996, entitled xe2x80x9cInteroperable Cryptographic Key Recovery Systemxe2x80x9d (xe2x80x9cJohnson et al. IIxe2x80x9d), assigned to the International Business Machines Corporation, is incorporated herein by reference. This cited patent application describes another key recovery system.
U.S. patent application of S. Chandersekaran et al., Ser. No. 08/971,204, now U.S. Pat. No. 6,355,972 filed Nov. 14, 1997, entitled xe2x80x9cFrame-Work Based Cryptographic Key Recovery Systemxe2x80x9d (xe2x80x9cChandersekaran et al.xe2x80x9d), assigned to the International Business Machines Corporation, is incorporated herein by reference. This cited patent application describes a key recovery system.
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private key ) encryption systems such as the Data Encryption Standard (DES) system use the same secret key for both encrypting and decrypting messages. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key ) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver""s public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies because the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (that is, systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving the key portions to the key recovery agents (in which case the key portions are said to be xe2x80x9cescrowedxe2x80x9d) or by providing sufficient information in the communication itself (as by encrypting the key portions) to allow the key recovery agents to regenerate the key portions. Key recovery agents would reveal the escrowed or regenerated key portions to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception. The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent.
Key recovery systems serve the communicants"" interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same time, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (such as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial files where keys are not recoverable. Loss of keys may result in loss of important stored data.
The term xe2x80x9ckey recoveryxe2x80x9d encompasses mechanisms that allow authorized third parties to retrieve the cryptographic keys used for data confidentiality, with the ultimate goal of recovery of encrypted data. There are two classes of key recovery mechanisms based on the ways keys are held to enable key recovery: key escrow and key encapsulation. Key escrow techniques are based on the paradigm that the government or a trusted third party called an xe2x80x9cescrow agent,xe2x80x9d holds the actual user keys or portions thereof. Key encapsulation techniques, on the other hand, are based on the paradigm that a cryptographically encapsulated form of the key is made available to third parties that require key recovery; the encapsulation technique ensures that only certain trusted third parties called xe2x80x9crecovery agentsxe2x80x9d can perform the unwrap operation to retrieve the key material buried inside. There may also be hybrid schemes that use some escrow mechanisms in addition to encapsulation mechanisms.
An orthogonal way to classify key recovery mechanisms is based on the nature of the key that is either escrowed or encapsulated. Some schemes rely on the escrow or encapsulation of long-term keys, such as private keys, while other schemes are based on the escrow or encapsulation of ephemeral keys such as session keys.
Since escrow schemes involve the actual archival of keys, they typically deal with long-term keys, in order to avoid the proliferation problem that arises when trying to archive myriad ephemeral keys. These long-term xe2x80x9cescrowedxe2x80x9d keys are then used to retrieve the ephemeral keys used for data confidentiality.
Key encapsulation techniques can also choose to archive the encapsulated keys, but usually they do not. Instead, these techniques usually operate on the ephemeral keys, and associate the encapsulated key with the actual enciphered message and thereby dispense with the archival process. The encapsulated key is put into a key recovery block that is generated by the party performing the data encryption, and associated with the encrypted data. To ensure the transmission and the integrity of the key recovery block, it may be required for processing by the party performing the data decryption. The processing mechanism ensures that successful data decryption cannot occur unless the key recovery block is processed successfully. Since the key recovery block has to be associated with the cryptographic session in some way, key encapsulation schemes may require the perturbation of the communication protocol used.
The process of cryptographic key recovery involves two major phases. First, parties that are involved in cryptographic associations have to perform an operation to enable key recovery (such as the escrow of use keys, or the generation of key recovery blocks, etc.)xe2x80x94this is typically called the xe2x80x9ckey recovery enablementxe2x80x9d phase. Next, authorized third parties that desire to recover the data keys do so with the help of a recovery server and one or more escrow agents or recovery agents; this is the actual xe2x80x9ckey recovery servicexe2x80x9d phase.
One desirable characteristic of key recovery systems is referred to as xe2x80x9cdispersion.xe2x80x9d A key recovery system having this feature requires the cooperation of multiple key recovery agents to recover a cryptography key. Because the cooperation of multiple key recovery agents is required, the possibility of abuse is reduced.
Schemes have been developed to enable the recovery of cryptographic keys using multiple agents in a key recovery system. In these systems, a key recovery block is generated to make a key recoverable only if all of the agents participate in the recovery process. If any agent is not available for any reason, then key recovery fails. This causes problems when a large scale deployment requires the use of many agents over a wide area network and not all agents are available all the time. Recoveries frequently fail because of the unavailability of one or more of the multiple key recovery agents.
The present invention is a method, apparatus, and computer program product for multiple agent key recovery where not all of the agents are required for the recovery process. The present invention defines a key recovery block that specifies allowable subsets of the total set of key recovery agents that can participate in a valid key recovery.
For each subset, key recovery information is computed and stored after the subset is specified. This key recovery information is only useable by the listed subset because it is computed using the public keys of that subset of agents.
When key recovery is initiated, a trusted processor (a key recovery coordinator) validates the contents of the key recovery block and it uses and is allowed to use any of the subsets of the agents to process the key recovery request. Since many subsets could be specified, the likelihood of key recovery failure is greatly diminished.
According to one aspect of the present invention, a method is provided for key recovery for use in a key recovery system having a set of key recovery agents to recover a cryptography key. The method includes the steps of receiving a key recovery request from a key recovery client; receiving a key recovery block containing a plurality of key recovery agent subsets, each containing a different subset of the key recovery agents in the set; determining the availability of the agents in one of the key recovery agent subsets; and, when all of the agents in that subset are determined to be available, requesting key information from those agents; receiving key information from those agents; generating a key based on the key information; and sending the key to the key recovery client.
According to another aspect of the present invention, a method is provided for generating a key recovery block in for use in a key recovery system having a set of key recovery agents to recover a cryptography key. The method includes the steps of generating a plurality of key recovery agent subsets, each containing a different subset of the key recovery agents in the set; generating key recovery information for each key recovery agent in each subset; and populating a key recovery block with the key recovery agent subsets and the key recovery information. According to one embodiment, the step of generating key recovery information includes the steps of encrypting the cryptography key using the public key of one of the key recovery agents to produce a result; and encrypting that result using the public key of a different one of the key recovery agents.
According to another aspect of the present invention, a key recovery block is provided for use in a key recovery system having a set of key recovery agents to recover a cryptography key. The key recovery block includes a subset number field that specifies a number of subsets S of the key recovery agents that can recover the cryptography key, and S subset fields. Each subset field has a key recovery agent number field that specifies the number of key recovery agents in the subset, and a plurality of key recovery agent fields, each specifying a key recovery agent and key recovery information for that key recovery agent.
Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.